package LeetCode热题HOT100;

import java.util.*;

public class p207课程表 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //拓扑排序的思路+BFS
        Map<Integer,Integer> inDegree=new HashMap<>();//记录每门课程，以及它对应的入度
        //1. 先将 课程-入度 全初始化为入度=0
        for (int i = 0; i <numCourses; i++) {
            inDegree.put(i,0);
        }

        //2.根据prerequisites 构建课程的依赖关系
        Map<Integer, List<Integer>> map=new HashMap<>();//先执行课程 —— 先执行课程对应的后执行课程顺序表

        for (int[] relate:prerequisites) {
            int before=relate[1];
            int after=relate[0];

            inDegree.put(after,inDegree.get(after)+1);//after 的入度需要加一，因为 after需要before课程先执行

            if (!map.containsKey(before)) {
                map.put(before,new ArrayList<>());
            }
            map.get(before).add(after);
        }

        //3.BFS，将入度=0的课程放入队列
        Queue<Integer> queue=new LinkedList<>();
        for (int key:inDegree.keySet()) {

            if (inDegree.get(key)==0) {
                queue.offer(key);
            }
        }

        // 取出一个节点, 对应学习这门课程.
        // 遍历当前邻接表, 更新其入度; 更新之后查看入度, 如果为0, 加入到队列
        while (!queue.isEmpty()) {
            int curCourse=queue.poll();
            if (!map.containsKey(curCourse)) {
                continue;
            }
            List<Integer> list = map.get(curCourse);
            for (int num:list) {
                inDegree.put(num,inDegree.get(num)-1);
                if (inDegree.get(num)==0) {
                    queue.offer(num);
                }
            }
        }

        for (int key:inDegree.keySet()) {
            if (inDegree.get(key)!=0) {
                return false;
            }
        }

        return true;

    }
}
